package com.gitee.feizns.explore.data_structure.heap;

/**
 * @author feizns
 * @since 2019/11/19
 */
public abstract class Utils {

    public static boolean isMinHeap(int[] arr, int ind) {
        int l = left(ind);
        int r = right(ind);
        if ( l < arr.length ) {
            if ( r < arr.length )
                return arr[ind] < arr[l] && arr[ind] < arr[r] && isMinHeap(arr, l) && isMinHeap(arr, r);
            return arr[ind] < arr[l] && isMinHeap(arr, l);
        }
        return true;
    }

    public static boolean isMaxHeap(int[] arr, int ind) {
        int l = left(ind);
        int r = right(ind);
        if ( l < arr.length ) {
            if ( r < arr.length )
                return arr[ind] > arr[l] && arr[ind] > arr[r] && isMaxHeap(arr, l) && isMaxHeap(arr, r);
            return arr[ind] > arr[l] && isMaxHeap(arr, l);
        }
        return true;
    }

    public static boolean isMinHeap(int[] arr) {
        return isMinHeap(arr, 0);
    }

    public static boolean isMaxHeap(int[] arr) {
        return isMaxHeap(arr, 0);
    }

    public static int parent(int index) {
        if ( index == 1 ) return 0;
        if ( index > 1 )
            return (index - 1) / 2;
        throw new RuntimeException("INDEX ...");
    }

    private static int left(int index) {
        return index * 2 + 1;
    }

    private static int right(int index) {
        return index * 2 + 2;
    }

}
